package com.tgy.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: tgy
 * @Date: 12/5/20 11:22 AM
 *
 * https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
 */
public class _297_二叉树的序列化与反序列化 {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {

        StringBuilder sb = new StringBuilder("[");

        if (root != null) {

            Queue<TreeNode> queue = new LinkedList<>();

            queue.offer(root);

            int height = 1,treeHeight = treeHeight(root), everyLevelNum = 1;

            while (!queue.isEmpty()) {

                TreeNode node = queue.poll();

                everyLevelNum--;

                if (node != null) {

                    queue.offer(node.left);
                    queue.offer(node.right);
                    sb.append(node.val +",");
                }else {

                    sb.append("null,");
                }

                if (everyLevelNum == 0) {


                    height++;

                    if (height > treeHeight) {

                        break;
                    }
                    everyLevelNum = queue.size();
                }

            }
        }

        if (sb.charAt(sb.length() - 1) == ',') {

            sb.deleteCharAt(sb.length() - 1);
        }

        sb.append("]");
        return sb.toString();
    }

    private int treeHeight(TreeNode root) {

        if (root == null) {

            return 0;
        }


        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int treeHeight = 0, everyLevel = 1;

        while (!queue.isEmpty()) {

            TreeNode node = queue.poll();

            everyLevel--;
            if (node.left != null) {

                queue.offer(node.left);
            }

            if (node.right != null){

                queue.offer(node.right);
            }

            if (everyLevel == 0) {

                treeHeight++;
                everyLevel = queue.size();
            }
        }

        return treeHeight;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        if (!data.startsWith("[") || !data.endsWith("]") || data.length() == 2) {

            return null;
        }


        String[] datas = data.substring(1, data.length() - 1).split(",");

        return deserialize(datas,0);
    }

    private TreeNode deserialize(String []datas,int index) {

        if (index >= datas.length || datas[index].equals("null")) {

            return null;
        }

        TreeNode node = new TreeNode(Integer.parseInt(datas[index]));
        int leftIndex = (index << 1) + 1;
        node.left =  deserialize(datas,leftIndex);
        node.right = deserialize(datas,leftIndex + 1);

        return node;
    }
}
